package suanfa;

import java.util.Arrays;

public class triangle {
    //给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
    //输入: nums = [2,2,3,4]
    //输出: 3
    //解释:有效的组合是:
    //2,3,4 (使用第一个 2)
    //2,3,4 (使用第二个 2)
    //2,2,3
    //示例 2:
    //
    //输入: nums = [4,2,3,4]
    //输出: 4
    // 现将原有的数组进行排序，先选定一个最大的值C，然后除去这个最大的值
    // 然后从数组的最左边开始，如果当前值加上右边的值大于左边的值（说明left向左的值都是大于除去的这个值的）
    // 所以个数ret+=right-left
    //然后right向左移动，C也向左移动，
    // 如果right的值加left小于C，则left向做移动（因为都是排过序的）
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ret=0,n=nums.length;
        for(int i=n-1;i>=2;i--){
            int right=i-1;
            int left=0;
            while(left<right){
                if(nums[left]+nums[right]>nums[i]){
                    ret+=right-left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }
}
